package com.test.daily.leetcode.y2022.m05.day0523.v05;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/23 上午 11:36
 * @version: 1.0
 */
public class Solution {
    public static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static int getMax(Node root) {
        ArrayList<Node> list = getPreList(root);
        HashMap<Node, Node> parentMap = putParent(root);
        int maxDistance = 0;
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = 0; j < list.size(); j++) {
                maxDistance = Math.max(maxDistance, distance(list.get(i), list.get(j), parentMap));
            }
        }
        return maxDistance;
    }

    public static int distance(Node o1, Node o2, HashMap<Node, Node> map) {
        HashSet<Node> o1Set = new HashSet<Node>();
        Node cur = o1;
        o1Set.add(cur);
        while (map.get(cur) != null) {
            cur = map.get(cur);
            o1Set.add(cur);
        }
        cur = o2;
        while (!o1Set.contains(cur)) {
            cur = map.get(cur);
        }
        Node commonFather = cur;
        int o1Height = 1;
        cur = o1;
        while (cur != commonFather) {
            cur = map.get(cur);
            o1Height++;
        }
        cur = o2;
        int o2Height = 1;
        while (o2 != commonFather) {
            cur = map.get(cur);
            o2Height++;
        }
        return o1Height + o2Height - 1;
    }

    public static HashMap<Node, Node> putParent(Node root) {
        if (root == null) {
            return null;
        }
        HashMap<Node, Node> parentMap = new HashMap<>();
        parentMap.put(root, null);
        parent(root, parentMap);
        return parentMap;
    }

    public static void parent(Node root, HashMap<Node, Node> map) {
        if (root.left != null) {
            map.put(root.left, root);
            parent(root.left, map);
        }
        if (root.right != null) {
            map.put(root.right, root);
            parent(root.right, map);
        }
    }

    public static ArrayList<Node> getPreList(Node root) {
        if (root == null) {
            return null;
        }
        ArrayList<Node> list = new ArrayList<>();
        preList(root, list);
        return list;
    }

    public static void preList(Node root, ArrayList<Node> list) {
        if (root.left != null) {
            list.add(root.left);
        }
        list.add(root);
        if (root.right != null) {
            list.add(root.right);
        }
    }
    public static class Info{
        int height;
        int maxDistance;
        public Info(int height, int maxDistance){
            this.height = height;
            this.maxDistance = maxDistance;
        }
    }
    public static Info process(Node head){
        if(head == null){
            return new Info(0,0);
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int p1 = leftInfo.maxDistance;
        int p2 = rightInfo.maxDistance;
        int p3 = leftInfo.height + rightInfo.height + 1;
        int maxDistance = Math.max(p1, Math.max(p2, p3));
        return new Info(height, maxDistance);
    }
    public static int maxDistance2(Node root){
        return process(root).maxDistance;
    }
}
